#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_

#include <iostream>
#include <LinkQueue.h>

class BinaryTree
{
public:
    using ElementType = int;
    BinaryTree();
    void Insert(const ElementType& element);
    void Remove(const ElementType& element);

    ElementType* FindByElement(const ElementType& element);

    void show();

private:
    struct Node
    {
        Node(const ElementType& data):data(data)
        {
            left = right = nullptr;
        }
        ElementType data; //数据域
        Node *left; //左孩子
        Node *right; //右孩子
    }; 

    Node *InsertNode(Node* node,const ElementType& element);
    Node* RemoveNode(Node* node,const ElementType& element);
    Node* GetMinNode(Node* node);


    ElementType* FindNode(Node* node,const ElementType& element);
    void PrevTree(Node* node);
    void MidTree(Node* node);
    void PostTree(Node* node);
    void HeightTravel();

    //AVL旋转
    //左旋
    Node* RotateRight(Node* node);
    //右旋
    Node* RotateLeft(Node* node);
    //左右旋
    Node* RotateLeftRight(Node* node);
    //右左旋
    Node* RotateRightLeft(Node* node);

    int GetNodeHeight(Node* node);
    int LRDevition(Node *node);
    Node *root;//根节点

};




#endif